package org.algorithm.YaYa;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和
 * https://leetcode.cn/problems/two-sum/
 */
public class SumOfTwoNumbers {

    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        Map<Integer,Integer> keyMap = new HashMap<Integer,Integer>(16);
        keyMap.put(nums[0],0);
        for (int i = 1; i < length-1; i++) {
            if(keyMap.containsKey(target-nums[i])){
                return new int[]{keyMap.get(target-nums[i]),i};
            }
            keyMap.put(nums[i],i);
        }
        return new int[0];
    }
    @Test
   public void printTwoSum(){
        int[] nums = new int[]{2,7,11,15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(nums,target)));
    }

    /**
     * 哈希表查找
     * 题解：哈希表：把元素存在map里面，形成哈希表，再去查找，例如
     * 数组：[3,5,1,6,4]  target=7
     * hashMap：针对数组第一个元素，前面什么也没有，直接put,key为元素值，value为索引,hashMap.put(nums[0],0)
     * 针对数组 i>1的元素，使用循环，放进去，key是元素值，value是索引
     * 终止条件：即hashMap中存在目标target-当前元素时，循环终止，返回当前元素下标以及hashMap里面target-当前元素的vaule
     * 7-5=2,hashMap里面现在只有一个3，不存在2，所以存放第二个元素hashMap.put(5,1)
     * 7-1=6 hashMap里面现在是3，5，没有6。hashMap.put(1,2)
     * 7-6=1 hashMap里面存在1的元素，循环终止，返回当前元素6的索引以及7-6=1的索引
     */
}
